# To run the program
#     main.py < Voting.in > Voting.out

# To document the program
#     pydoc -w main

# -------
# globals
# -------

candidates = {} # mapping of candidate number to a name
votes = {} # mapping of candidate number to a list of ballots[], which are indices of voters who voted for that candidate
ballots = [] # 2D list of ballots with each row corresponding to one voter's ballot, and the columns to their picks in descending order.
won = False # boolean value to keep track of whether or not a winner has been found



# -------
# my_read
# -------

def voting_read (r) :
    """
    reads in the input and stores the candidates and ballots
    """
    global candidates,votes,ballots
    
    votes.clear()
    candidates.clear()
    ballots = []
    
    try :
        for i in range(0,int(r.read())) :  # r.read() = number of candidates
          candidates[i] = r.read()  # stores candidates names
          votes[i] = []
        
        s = r.read()        
        while ( s != '') :     
          ballots += [s.split()]  # storing votes
          s = r.read()
          
    except EOFError :
      pass    

# -------
# voting_eval
# -------

def voting_eval () :
    """
    counts all of the votes inputted, and then  checks for a winner.
    Eliminates losers until a winner is found, or until a tie is reached
    """
    global candidates,votes,ballots,won
    
    for i in range(0,len(ballots)) :  # count up votes                 
      votes[int(ballots[i][0]) - 1] += [i]  # add this ballot to the votes for this candidate          
    
    won = False
    # check for winner or eliminate candidates
    while(not won) :
      for k in votes.keys() :  # checking for majority winner
        k = int(k)      
        if ( len(votes[k]) > len(ballots)/2) :
          won = True
          votes = {k:votes[k]}
          candidates = { k : candidates[k] }
          break
      
      votes_list = [len(v) for v in votes.values()]
      min_votes = min(votes_list)
      max_votes = max(votes_list)
      
      if ( not won ) : # we check for a tie
          if ( min_votes == max_votes ) :
            won = True
            
      if ( not won ) :  # we eliminate losers and reset the vote count
        eliminated = []
        for i in votes.keys() :
          if ( len(votes[i]) == min_votes ) :  # Keep eliminating candidates
            candidates.pop(i)
            eliminated += votes.pop(i)
        for e in eliminated :
          while((int(ballots[e][0]) - 1) not in votes) :
            ballots[e].pop(0)
          votes[int(ballots[e][0]) - 1] += [e]

# --------
# voting_print
# --------

def voting_print (w) :
    """
    outputs the winner (or winners in the case of a tie that results in multiple winners)
    """
    w.write(candidates.values())

